"""3.归并排序"""
def merge_sort(arr):
    """
    归并排序算法
    """
    if len(arr) <= 1:
        return arr

    # 分：将数组分成两半
    mid = len(arr) // 2
    left_half = merge_sort(arr[:mid])
    right_half = merge_sort(arr[mid:])

    # 治：合并两个有序数组
    return merge(left_half, right_half)


def merge(left, right):
    """
    合并两个有序数组
    """
    result = []
    i = j = 0

    # 比较两个数组的元素，按顺序合并
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    # 添加剩余元素
    result.extend(left[i:])
    result.extend(right[j:])

    return result


def merge_sort_in_place(arr, left=0, right=None, temp=None):
    """
    原地归并排序（减少空间复杂度）
    """
    if right is None:
        right = len(arr) - 1
        temp = [0] * len(arr)

    if left < right:
        mid = (left + right) // 2

        # 递归排序左右两半
        merge_sort_in_place(arr, left, mid, temp)
        merge_sort_in_place(arr, mid + 1, right, temp)

        # 合并两个有序部分
        merge_in_place(arr, left, mid, right, temp)


def merge_in_place(arr, left, mid, right, temp):
    """
    原地合并两个有序子数组
    """
    i, j, k = left, mid + 1, left

    # 比较并合并
    while i <= mid and j <= right:
        if arr[i] <= arr[j]:
            temp[k] = arr[i]
            i += 1
        else:
            temp[k] = arr[j]
            j += 1
        k += 1

    # 复制剩余元素
    while i <= mid:
        temp[k] = arr[i]
        i += 1
        k += 1

    while j <= right:
        temp[k] = arr[j]
        j += 1
        k += 1

    # 将临时数组复制回原数组
    for i in range(left, right + 1):
        arr[i] = temp[i]


# 测试归并排序
print("=== 归并排序测试 ===")
arr = [38, 27, 43, 3, 9, 82, 10]
print(f"原数组: {arr}")

sorted_arr = merge_sort(arr.copy())
print(f"归并排序结果: {sorted_arr}")

merge_sort_in_place(arr)
print(f"原地归并排序结果: {arr}")
print()